Cwiczenie 7

/* Cwiczenie 7 */

#include <stdio.h>
#include <stdlib.h>  /* Funkcja system()         */
#include <assert.h>  /* Makroinstrukcja assert() */
#include <math.h>    /* Funkcja log()            */

typedef unsigned int uint;
typedef char bool;

#define true 1
#define false 0
#define MAX_PIERWSZA 10000000    /* Rozmiar tablicy prawdy */

bool czyPierwsza(uint liczba) {
    static bool pierwsze[MAX_PIERWSZA];  /* Talica prawdy     */
    static bool init = false;            /* Zainicjalizowana? */

    assert(liczba < MAX_PIERWSZA);

    if (!init) {
        uint i, j;   /* Liczniki petli */

        pierwsze[0] = false;
        pierwsze[1] = false;

        for (i = 2; i < MAX_PIERWSZA; i++)
            pierwsze[i] = true;

        for (i = 2; i < MAX_PIERWSZA; i++)
            for (j = 2*i; j < MAX_PIERWSZA; j += i)
                pierwsze[j] = false;

        init = true;
    }

    return pierwsze[liczba];
}

uint pi(uint n) {
    static uint ilosc = 0;   /* Licznik liczb pierwszych    */
    static uint iloscDo = 0; /* Do jakiej liczby policzono? */
    uint i;                  /* Licznik petli               */

    /* Dzieki zmiennym statycznym funkcja bedzie dzialac    */
    /* duzo szybciej.                                       */

    if (n < iloscDo) {
        ilosc = 0;
        iloscDo = 0;
    }

    for (i=iloscDo+1; i<=n; i++)
        if ( czyPierwsza(i) )
            ilosc++;

    iloscDo = n;

    return ilosc;
}

uint f(uint n) {
    return n / log(n);
}

void print(uint n) {
    uint pin = pi(n);
    uint fn = f(n);
    uint deltan = pin-fn;

    printf("pi(%u) = %u\tf(%u) = %u\t(pi-f)(%u) = %u\n",
            n, pin, n, fn, n, deltan );
}

int main(void) {
    uint i;

    for (i = 10000; i<=1000000; i += 10000)
        print(i);

    return 0;
}